class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int> mem(n);
        int ret=0;
        for(int i=0;i<nums.size();i++)
            ret=max(ret,dfs(i,nums,mem));
        return ret;
    }
    int dfs(int pos,vector<int>& nums,vector<int>& mem)
    {
        if(mem[pos]!=0)return mem[pos];

        int ret=1;
        for(int i=pos+1;i<nums.size();i++)
        {
            if(nums[i]>nums[pos])
            {
                ret=max(ret,dfs(i,nums,mem)+1);
            }
        }
        mem[pos]=ret;
        return mem[pos];
    }
};
